﻿#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[1010][1010];

int arr[1010][3];

int main()
{
    int n, V;
    cin >> n >> V;
    for (size_t i = 1; i <= n; i++) {
        cin >> arr[i][1];
        cin >> arr[i][2];
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (j - arr[i][1] >= 0)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i][1]] + arr[i][2]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }

        }
    }
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= V; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << dp[n][V] << endl;
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int j = 1; j <= V; j++) {
        dp[0][j] = -1;
    }
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= V; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (j - arr[i][1] >= 0 && dp[i - 1][j - arr[i][1]] != -1) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i][1]] + arr[i][2]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    for (size_t i = 0; i <= n; i++)
    {
        for (size_t j = 0; j <= V; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << dp[n][V];


    return 0;
}